home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 23 / CU Amiga - Super CD-ROM 23 (June 1998).iso / CUCD / Games / ADoomPPC / src / z_zone.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-31  |  9.2 KB  |  468 lines
  1. // Emacs style mode select   -*- C++ -*- 
  2. //-----------------------------------------------------------------------------
  3. //
  4. // $Id:$
  5. //
  6. // Copyright (C) 1993-1996 by id Software, Inc.
  7. //
  8. // This source is available for distribution and/or modification
  9. // only under the terms of the DOOM Source Code License as
  10. // published by id Software. All rights reserved.
  11. //
  12. // The source is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  15. // for more details.
  16. //
  17. // $Log:$
  18. //
  19. // DESCRIPTION:
  20. //    Zone Memory Allocation. Neat.
  21. //
  22. //-----------------------------------------------------------------------------
  23.  
  24. static const char
  25. rcsid[] = "$Id: z_zone.c,v 1.4 1997/02/03 16:47:58 b1 Exp $";
  26.  
  27. #include "z_zone.h"
  28. #include "i_system.h"
  29. #include "doomdef.h"
  30.  
  31.  
  32. //
  33. // ZONE MEMORY ALLOCATION
  34. //
  35. // There is never any space between memblocks,
  36. //  and there will never be two contiguous free memblocks.
  37. // The rover can be left pointing at a non-empty block.
  38. //
  39. // It is of no value to free a cachable block,
  40. //  because it will get overwritten automatically if needed.
  41. // 
  42.  
  43. #define ZONEID    0x1d4a11
  44.  
  45.  
  46. typedef struct
  47. {
  48.     // total bytes malloced, including header
  49.     int        size;
  50.  
  51.     // start / end cap for linked list
  52.     memblock_t    blocklist;
  53.     
  54.     memblock_t*    rover;
  55.     
  56. } memzone_t;
  57.  
  58.  
  59.  
  60. memzone_t*    mainzone;
  61.  
  62.  
  63.  
  64. //
  65. // Z_ClearZone
  66. //
  67. void Z_ClearZone (memzone_t* zone)
  68. {
  69.     memblock_t*        block;
  70.     
  71.     // set the entire zone to one free block
  72.     zone->blocklist.next =
  73.     zone->blocklist.prev =
  74.     block = (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
  75.     
  76.     zone->blocklist.user = (void *)zone;
  77.     zone->blocklist.tag = PU_STATIC;
  78.     zone->rover = block;
  79.     
  80.     block->prev = block->next = &zone->blocklist;
  81.     
  82.     // NULL indicates a free block.
  83.     block->user = NULL;    
  84.  
  85.     block->size = zone->size - sizeof(memzone_t);
  86. }
  87.  
  88.  
  89.  
  90. //
  91. // Z_Init
  92. //
  93. void Z_Init (void)
  94. {
  95.     memblock_t*    block;
  96.     int        size;
  97.  
  98.     mainzone = (memzone_t *)I_ZoneBase (&size);
  99.     mainzone->size = size;
  100.  
  101.     // set the entire zone to one free block
  102.     mainzone->blocklist.next =
  103.     mainzone->blocklist.prev =
  104.     block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) );
  105.  
  106.     mainzone->blocklist.user = (void *)mainzone;
  107.     mainzone->blocklist.tag = PU_STATIC;
  108.     mainzone->rover = block;
  109.     
  110.     block->prev = block->next = &mainzone->blocklist;
  111.  
  112.     // NULL indicates a free block.
  113.     block->user = NULL;
  114.     
  115.     block->size = mainzone->size - sizeof(memzone_t);
  116. }
  117.  
  118.  
  119. //
  120. // Z_Free
  121. //
  122. void Z_Free (void* ptr)
  123. {
  124.     memblock_t*        block;
  125.     memblock_t*        other;
  126.     
  127.     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
  128.  
  129.     if (block->id != ZONEID)
  130.     I_Error ("Z_Free: freed a pointer without ZONEID");
  131.         
  132.     if (block->user > (void **)0x100)
  133.     {
  134.     // smaller values are not pointers
  135.     // Note: OS-dependend?
  136.     
  137.     // clear the user's mark
  138.     *block->user = 0;
  139.     }
  140.  
  141.     // mark as free
  142.     block->user = NULL;    
  143.     block->tag = 0;
  144.     block->id = 0;
  145.     
  146.     other = block->prev;
  147.  
  148.     if (!other->user)
  149.     {
  150.     // merge with previous free block
  151.     other->size += block->size;
  152.     other->next = block->next;
  153.     other->next->prev = other;
  154.  
  155.     if (block == mainzone->rover)
  156.         mainzone->rover = other;
  157.  
  158.     block = other;
  159.     }
  160.     
  161.     other = block->next;
  162.     if (!other->user)
  163.     {
  164.     // merge the next free block onto the end
  165.     block->size += other->size;
  166.     block->next = other->next;
  167.     block->next->prev = block;
  168.  
  169.     if (other == mainzone->rover)
  170.         mainzone->rover = block;
  171.     }
  172. }
  173.  
  174.  
  175.  
  176. //
  177. // Z_Malloc
  178. // You can pass a NULL user if the tag is < PU_PURGELEVEL.
  179. //
  180. #define MINFRAGMENT        64
  181.  
  182.  
  183. void*
  184. Z_Malloc
  185. ( int        size,
  186.   int        tag,
  187.   void*        user )
  188. {
  189.     int        extra;
  190.     memblock_t*    start;
  191.     memblock_t* rover;
  192.     memblock_t* newblock;
  193.     memblock_t*    base;
  194.  
  195.     size = (size + 31) & ~31;
  196.     
  197.     // scan through the block list,
  198.     // looking for the first free block
  199.     // of sufficient size,
  200.     // throwing out any purgable blocks along the way.
  201.  
  202.     // account for size of block header
  203.     size += sizeof(memblock_t);
  204.     
  205.     // if there is a free block behind the rover,
  206.     //  back up over them
  207.     base = mainzone->rover;
  208.     
  209.     if (!base->prev->user)
  210.     base = base->prev;
  211.     
  212.     rover = base;
  213.     start = base->prev;
  214.     
  215.     do
  216.     {
  217.     if (rover == start)
  218.     {
  219.         // scanned all the way around the list
  220.         I_Error ("Z_Malloc: failed on allocation of %i bytes", size);
  221.     }
  222.     
  223.     if (rover->user)
  224.     {
  225.         if (rover->tag < PU_PURGELEVEL)
  226.         {
  227.         // hit a block that can't be purged,
  228.         //  so move base past it
  229.         base = rover = rover->next;
  230.         }
  231.         else
  232.         {
  233.         // free the rover block (adding the size to base)
  234.  
  235.         // the rover can be the base block
  236.         base = base->prev;
  237.         Z_Free ((byte *)rover+sizeof(memblock_t));
  238.         base = base->next;
  239.         rover = base->next;
  240.         }
  241.     }
  242.     else
  243.         rover = rover->next;
  244.     } while (base->user || base->size < size);
  245.  
  246.     
  247.     // found a block big enough
  248.     extra = base->size - size;
  249.     
  250.     if (extra >  MINFRAGMENT)
  251.     {
  252.     // there will be a free fragment after the allocated block
  253.     newblock = (memblock_t *) ((byte *)base + size );
  254.     newblock->size = extra;
  255.     
  256.     // NULL indicates free block.
  257.     newblock->user = NULL;    
  258.     newblock->tag = 0;
  259.     newblock->prev = base;
  260.     newblock->next = base->next;
  261.     newblock->next->prev = newblock;
  262.  
  263.     base->next = newblock;
  264.     base->size = size;
  265.     }
  266.     
  267.     if (user)
  268.     {
  269.     // mark as an in use block
  270.     base->user = user;
  271.     *(void **)user = (void *) ((byte *)base + sizeof(memblock_t));
  272.     }
  273.     else
  274.     {
  275.     if (tag >= PU_PURGELEVEL)
  276.         I_Error ("Z_Malloc: an owner is required for purgable blocks");
  277.  
  278.     // mark as in use, but unowned    
  279.     base->user = (void *)2;        
  280.     }
  281.     base->tag = tag;
  282.  
  283.     // next allocation will start looking here
  284.     mainzone->rover = base->next;    
  285.     
  286.     base->id = ZONEID;
  287.     
  288.     return (void *) ((byte *)base + sizeof(memblock_t));
  289. }
  290.  
  291.  
  292.  
  293. //
  294. // Z_FreeTags
  295. //
  296. void
  297. Z_FreeTags
  298. ( int        lowtag,
  299.   int        hightag )
  300. {
  301.     memblock_t*    block;
  302.     memblock_t*    next;
  303.     
  304.     for (block = mainzone->blocklist.next ;
  305.      block != &mainzone->blocklist ;
  306.      block = next)
  307.     {
  308.     // get link before freeing
  309.     next = block->next;
  310.  
  311.     // free block?
  312.     if (!block->user)
  313.         continue;
  314.     
  315.     if (block->tag >= lowtag && block->tag <= hightag)
  316.         Z_Free ( (byte *)block+sizeof(memblock_t));
  317.     }
  318. }
  319.  
  320.  
  321.  
  322. //
  323. // Z_DumpHeap
  324. // Note: TFileDumpHeap( stdout ) ?
  325. //
  326. void
  327. Z_DumpHeap
  328. ( int        lowtag,
  329.   int        hightag )
  330. {
  331.     memblock_t*    block;
  332.     
  333.     printf ("zone size: %i  location: %p\n",
  334.         mainzone->size,mainzone);
  335.     
  336.     printf ("tag range: %i to %i\n",
  337.         lowtag, hightag);
  338.     
  339.     for (block = mainzone->blocklist.next ; ; block = block->next)
  340.     {
  341.     if (block->tag >= lowtag && block->tag <= hightag)
  342.         printf ("block:%p    size:%7i    user:%p    tag:%3i\n",
  343.             block, block->size, block->user, block->tag);
  344.         
  345.     if (block->next == &mainzone->blocklist)
  346.     {
  347.         // all blocks have been hit
  348.         break;
  349.     }
  350.     
  351.     if ( (byte *)block + block->size != (byte *)block->next)
  352.         printf ("ERROR: block size does not touch the next block\n");
  353.  
  354.     if ( block->next->prev != block)
  355.         printf ("ERROR: next block doesn't have proper back link\n");
  356.  
  357.     if (!block->user && !block->next->user)
  358.         printf ("ERROR: two consecutive free blocks\n");
  359.     }
  360. }
  361.  
  362.  
  363. //
  364. // Z_FileDumpHeap
  365. //
  366. void Z_FileDumpHeap (FILE* f)
  367. {
  368.     memblock_t*    block;
  369.     
  370.     fprintf (f,"zone size: %i  location: %p\n",mainzone->size,mainzone);
  371.     
  372.     for (block = mainzone->blocklist.next ; ; block = block->next)
  373.     {
  374.     fprintf (f,"block:%p    size:%7i    user:%p    tag:%3i\n",
  375.          block, block->size, block->user, block->tag);
  376.         
  377.     if (block->next == &mainzone->blocklist)
  378.     {
  379.         // all blocks have been hit
  380.         break;
  381.     }
  382.     
  383.     if ( (byte *)block + block->size != (byte *)block->next)
  384.         fprintf (f,"ERROR: block size does not touch the next block\n");
  385.  
  386.     if ( block->next->prev != block)
  387.         fprintf (f,"ERROR: next block doesn't have proper back link\n");
  388.  
  389.     if (!block->user && !block->next->user)
  390.         fprintf (f,"ERROR: two consecutive free blocks\n");
  391.     }
  392. }
  393.  
  394.  
  395.  
  396. //
  397. // Z_CheckHeap
  398. //
  399. void Z_CheckHeap (void)
  400. {
  401.     memblock_t*    block;
  402.     
  403.     for (block = mainzone->blocklist.next ; ; block = block->next)
  404.     {
  405.     if (block->next == &mainzone->blocklist)
  406.     {
  407.         // all blocks have been hit
  408.         break;
  409.     }
  410.     
  411.     if ( (byte *)block + block->size != (byte *)block->next)
  412.         I_Error ("Z_CheckHeap: block size does not touch the next block\n");
  413.  
  414.     if ( block->next->prev != block)
  415.         I_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
  416.  
  417.     if (!block->user && !block->next->user)
  418.         I_Error ("Z_CheckHeap: two consecutive free blocks\n");
  419.     }
  420. }
  421.  
  422.  
  423.  
  424.  
  425. //
  426. // Z_ChangeTag
  427. //
  428. void
  429. Z_ChangeTag2
  430. ( void*        ptr,
  431.   int        tag )
  432. {
  433.     memblock_t*    block;
  434.     
  435.     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
  436.  
  437.     if (block->id != ZONEID)
  438.     I_Error ("Z_ChangeTag: freed a pointer without ZONEID");
  439.  
  440.     if (tag >= PU_PURGELEVEL && (unsigned)block->user < 0x100)
  441.     I_Error ("Z_ChangeTag: an owner is required for purgable blocks");
  442.  
  443.     block->tag = tag;
  444. }
  445.  
  446.  
  447.  
  448. //
  449. // Z_FreeMemory
  450. //
  451. int Z_FreeMemory (void)
  452. {
  453.     memblock_t*        block;
  454.     int            free;
  455.     
  456.     free = 0;
  457.     
  458.     for (block = mainzone->blocklist.next ;
  459.      block != &mainzone->blocklist;
  460.      block = block->next)
  461.     {
  462.     if (!block->user || block->tag >= PU_PURGELEVEL)
  463.         free += block->size;
  464.     }
  465.     return free;
  466. }
  467.  
  468.